1. Field
The present invention relates to a path planning apparatus of a robot and a method thereof, and more particularly to a path planning apparatus of a robot, in which a path planning algorithm to control the movement of the robot is improved, and a method thereof.
2. Description of the Related Art
Robots are machines, which automatically perform work or manipulation of objects, and are used to assist humans in various fields. There are many types of robots, such as a humanoid robot, a mobile robot, an industrial robot, an operating robot, etc.
It is important to control motions of a robot to perform a duty or service given to the robot. A technique to treat the motions of the robot is fundamentally based on a path planning algorithm. In the field of robotics, path planning is also referred to as motion planning.
As the path planning algorithm, a rapidly-exploring random tree (RRT) algorithm is generally used if a degree of freedom is high or there is a complicated constraint.
The conventional RRT algorithm makes a tree using random search in a configuration space (hereinafter, referred to as a C-space).
As shown in FIG. 1, the conventional RRT algorithm is an algorithm, which is visualized as a tree T, in which a robot or a configuration of its components is expressed by one point in a C-space, and a path satisfying a constraint is searched from an initial configuration qinit to a final configuration q. Here, the extension of the tree T is achieved by repeating a process, in which a node qnear out of nodes included in the tree T, being the nearest to a configuration q, randomly sampled in the C-space, is selected and a new node qnew, separated from the nearest node qnear by a designated distance d, is selected. Now, the extension of the tree T will be described in detail.
With reference to FIG. 2A, for a tree 1 T1, to reach a final configuration G from an initial configuration qinit while avoiding a space K not satisfying the constraint of the C-space is generated, a node qnear, being the nearest to a sampled configuration q, is selected and is connected to the sampled configuration q, thus extending the tree 1 T1. Thereafter, as shown in FIG. 2B, the node qnear, being the nearest to a sampled configuration q, is connected to the sampled configuration q, thus extending a tree 2 T2. In the same manner, as shown in FIG. 2C, a node qnear, being the nearest to a sampled configuration q, is connected to the sampled configuration q, thus extending a tree 3 T3. When a tree 4 T4 is extended by connecting a node qnear′, being the nearest to a sampled configuration q, with the sampled configuration q and sequentially including a node qnew′, separated from the nearest node qnear′ by a designated distance d, in the fourth tree T4, as shown in FIG. 2D, the new node qnew′ is selected from a line connecting the nearest node qnear′ and the randomly sampled configuration q. Therefore, when the new node qnew′ is separated from the nearest node qnear by the designated distance d is located in a space K not satisfying the constraint, the extension of the tree 4 T4 toward the sampled configuration q is stopped and new sampling is performed again. Such a conventional RRT algorithm generates a path while extending the tree to satisfy the constraint.
However, since in the conventional RRT algorithm, the tree is extended by selecting the nearest node qnear only in consideration of distance, most edges of the tree are stretched in a shape close to a perpendicular line and thus the generated tree may be formed in a zigzag shape or excessively detour. The result is that the traveling distance of the robot is elongated or steeply curved portions are increased.
In order to apply the conventional RRT algorithm to a robot requiring simple, smooth, and natural movements, an additional process of smoothing a path generated from the RRT algorithm is required.